UVa/12317 - Document Compression/12317.2.cpp

   1 // Equipo Poncho, Carriel y Ruana
   2 // Accepted on UVa
   3 using namespace std;
   4 #include <algorithm>
   5 #include <iostream>
   6 #include <iterator>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 template <class T> string toStr(const T &x)
  24 { stringstream s; s << x; return s.str(); }
  25 template <class T> int toInt(const T &x)
  26 { stringstream s; s << x; int r; s >> r; return r; }
  27
  28 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  29 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  30 #define D(x) cout << #x " = " << (x) << endl;
  31
  32 const double EPS = 1e-9;
  33
  34 int cmp(double x, double y = 0, double tol = EPS) {
  35     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  36 }
  37
  38
  39 namespace IO {
  40 #define MAXBUFF (1<<18)
  41    char buffer[MAXBUFF], *p = buffer+MAXBUFF;
  42    char buffer2[MAXBUFF], *p2 = buffer2;
  43
  44    inline char read_char() {
  45       if( p == buffer+MAXBUFF ) {
  46          fread( buffer, 1, MAXBUFF, stdin );
  47          p = buffer;
  48       }
  49       return *p++;
  50    }
  51
  52    inline int read_int() {
  53       char c;
  54       while( !isdigit(c = read_char()) );
  55       int ret = c-'0';
  56       while( isdigit(c = read_char()) ) ret = ret * 10 + c-'0';
  57       return ret;
  58    }
  59
  60    void flush() {
  61       fwrite( buffer2, 1, p2-buffer2, stdout );
  62       p2 = buffer2;
  63    }
  64
  65    inline void write( char c ) {
  66       if( p2 == buffer2+MAXBUFF ) {
  67          fwrite( buffer2, 1, MAXBUFF, stdout );
  68          p2 = buffer2;
  69       }
  70       *p2++ = c;
  71    }
  72 }
  73
  74
  75
  76 const int MAXBASES = 105, oo = 1 << 28;
  77 int bases[MAXBASES];
  78
  79 int B, D;
  80 int dp[MAXBASES][1 << 16];
  81
  82 int docSize;
  83
  84 void binary(int x){
  85     for (int i = 0; i < 16; ++i){
  86         printf("%d", !!(x & (1 << i)));
  87     }
  88 }
  89
  90 void precompute(){
  91     for (int i = 0; i <= B; ++i) {
  92         for (int mask = 0; mask < (1 << 16); ++mask) {
  93             dp[i][mask] = oo;
  94         }
  95     }
  96     dp[0][0] = 0;
  97
  98     for (int i = 0; i < B; ++i) {
  99         for (int mask = 0; mask < (1 << 16); ++mask) {
 100             if (dp[i][mask] >= oo) continue;
 101
 102             int base = bases[i];
 103             dp[i+1][mask] = min(dp[i+1][mask], dp[i][mask]);
 104             dp[i+1][mask | base] = min(dp[i+1][mask | base], dp[i][mask] + 1);
 105         }
 106     }
 107 }
 108
 109 int main(){
 110     while (true) {
 111         B = IO::read_int();
 112         D = IO::read_int();
 113         if (B == 0 and D == 0) break;
 114         for (int i = 0; i < B; ++i) {
 115             bases[i] = 0;
 116
 117             int k = IO::read_int();
 118             while (k--) {
 119                 int x = IO::read_int(); x--;
 120                 bases[i] |= (1 << x);
 121             }
 122         }
 123         precompute();
 124         for (int j = 0; j < D; ++j) {
 125             int doc = 0;
 126             int k = IO::read_int();
 127             while (k--) {
 128                 int x = IO::read_int(); x--;
 129                 doc |= (1 << x);
 130             }
 131
 132             int ans = dp[B][doc];
 133             if (ans >= oo) ans = 0;
 134             printf("%d", ans);
 135
 136             if (j + 1 < D) printf(" ");
 137         }
 138         puts("");
 139     }
 140     IO::flush();
 141     return 0;
 142 }